/****************************************************************
 * 顺序表
 * 
 * 线性表的顺序存储
 * 
 * Notes:
 *      1。结构体的比较不能直接用等号，必须让结构体中的每一个值分别比较
 ****************************************************************/

#include <cstdlib>                   //包含了malloc和free函数
typedef int ElemType;                        //定义元素的类型

/****************************************************************
 * 1.1.1
 * 线性表的顺序存储类型描述(数组静态分配)
 * */
#define MaxSize 50                  //定义线性表的最大长度
typedef struct{
    ElemType data[MaxSize];         //顺序表的元素
    int length;                     //顺序表的当前长度
}SqList;                            //顺序表的类型定义

/**
 * 初始化顺序表(数组静态分配)
 * */
void InitList(SqList &L){
    for(int i = 0; i < MaxSize; i++)
        L.data[i] = 0;              //设置默认初始值
    L.length = 0;                   //设置初始当前长度为0
}

/*
 * 插入操作
 * */
bool ListInsert(SqList &L, int i, ElemType e){      //i 表示位序
    if(i < 1 || i > L.length + 1)                   //判断i的范围是否有效
        return false;
    if(L.length >= MaxSize)                         //当前存储空间已满，不能插入（是否应该是L.length + 1 >= MaxSize）
        return false;
    for(int j = L.length; j >= i; j--)              //将第i个元素及之后的元素后移
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;                              //在位置i处放入e
    L.length++;                                     //线性表的长度加1

    return true;  
}

/*
 * 删除操作
 * */
bool ListDelete(SqList &L, int i, ElemType &e){
    if(i < 1 || i > L.length)                       //判断i的范围是否有效
        return false;    
    e = L.data[i - 1];                              //将被删除的元素赋值给e
    for(int j = i; j < L.length; j++)               //将第i个位置后的元素前移
        L.data[j - 1] = L.data[j]; 
    L.length--;                                     //线性表长度减1

    return true;  
}

/*
 * 按位查找(顺序查找)
 * */
ElemType GetElem(SqList L, int i){                  // i 表示位序
    if(i < 1 || i > L.length)                       // 判断 i 的范围是否有效
        return -1;                                  // 若 i 的范围无效，则返回 -1
    return L.data[i - 1];
}

/*
 * 按值查找(顺序查找)
 * 在顺序表L中查找第一个值为e的元素，并返回其位序
 * */
int LocateElem(SqList L, ElemType e){
    for(int i = 0; i < L.length; i++)
        if(L.data[i] == e)
            return i + 1;                           //下标为i的元素值等于e,返回其位序i+1

    return 0;                                       //退出循环，说明查找失败
}

/****************************************************************
 * 1.1.2
 * 线性表的顺序存储类型描述(数组动态分配)
 * */
#define InitSize 100                //表长度的初始定义
typedef struct{
    ElemType *data;                 //指示动态分配数组的指针
    int Maxsize,length;             //数组的最大容量和当前个数
}SeqList;                           //动态分配数组顺序表的类型定义

/**
 * 初始化顺序表(数组动态分配)
 * */
void InitList(SeqList &L){
    L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);               //C语言的初始，释放动态分配语句malloc, free
    //L.data = new ElemType[InitSize];                                       //C++的初始,释放动态分配语句 new, delete
    L.length = 0;
    L.Maxsize = InitSize;
}
/**
 * 增加动态数组的长度(数组动态分配)
 * */
void IncreaseSize(SeqList &L, int len){
    int *p = L.data;
    L.data = (ElemType *)malloc(sizeof(ElemType) * (L.Maxsize + len));
    for(int i = 0; i < L.length; i++)
        L.data[i] = p[i];           //将数据复制到新区域
    L.Maxsize += len;               //更新数组的最大容量

    free(p);                        //释放旧的空间
}

/*
 * 按位查找(动态数组分配)
 * */
ElemType GetElem(SqList L, int i){                  // i 表示位序
    if(i < 1 || i > L.length)                       // 判断 i 的范围是否有效
        return -1;                                  // 若 i 的范围无效，则返回 -1
    return L.data[i - 1];
}
    


/**************************************************************** 
 * 测试程序 
 * */

int test(){
    SeqList L;          
    InitList(L);
    IncreaseSize(L,10);
    return 0;
}